/**
 * 赫夫曼结点构造函数
 * @param {String} data 结点值
 * @param {Number} weight 结点权值
 * @param {TreeNode} left 左孩子
 * @param {TreeNode} right 右孩子
 * @param {TreeNode} parent 双亲结点
 */
function TreeNode(data, weight, left, right, parent) {
	this.data = data;
	this.weight = weight;
	this.left = left;
	this.right = right;
	this.parent = parent;
}

/**
 * 赫夫曼树构造函数
 * @param {Array<TreeNode>} nodes 传入一个带权结点的集合用于构造赫夫曼树
 */
function HuffmanCode(nodes) {
	// 先把传入结点复制一份作为叶子结点属性，便于后续检索（数组中存放的是引用而非结点的深复制）
	this.leaves = new Array();
	for (let item of nodes) {
		this.leaves.push(item);
	}
	while (nodes.length > 1) {
		// 找出权重最小结点
		let minium = nodes[0];
		let miniumIndex = 0;
		for (let i = 1; i < nodes.length; i++) {
			if (nodes[i].weight < minium.weight) {
				minium = nodes[i];
				miniumIndex = i;
			}
		}
		// 从列表中移除权重最小结点
		nodes.splice(miniumIndex, 1);
		// 再找权重第二小的结点
		let penultimate = nodes[0];
		let penultimateIndex = 0;
		for (let i = 1; i < nodes.length; i++) {
			if (nodes[i].weight < penultimate.weight) {
				penultimate = nodes[i];
				penultimateIndex = i;
			}
		}
		// 从列表移除第二小的结点
		nodes.splice(penultimateIndex, 1);
		// 两者左右孩子构成一个二叉树，小的在左大的在右
		let newTreeRoot = new TreeNode(null, minium.weight + penultimate.weight, minium, penultimate, null);
		// 记得把两个结点的双亲结点设一下
		minium.parent = newTreeRoot;
		penultimate.parent = newTreeRoot;
		// 新二叉树根结点加入结点集合
		nodes.push(newTreeRoot);
	}
	// 最后，集合中只有一个结点就是赫夫曼树的根结点
	this.root = nodes[0];
	/**
	 * 获取全部字符编码的Map映射表
	 * @returns 每个字符对编码的映射表
	 */
	this.getAllCharCode = () => {
		let result = new Map();
		// 遍历每个叶子结点，逆向向上求编码
		for (let node of this.leaves) {
			let code = '';
			// 一直往上直至双亲结点为null时说明到了根节点
			for (let current = node; current.parent != null; current = current.parent) {
				// 判断当前结点是其双亲结点的左孩子还是右孩子
				if (current == current.parent.left) {
					// 由于是逆向编码，因此我们要按照正常读的时候反着来
					code = 0 + code;
				} else {
					code = 1 + code;
				}
			}
			// 记录到结果集
			result.set(node.data, code);
		}
		return result;
	}
}

// 测试一下
// 构造赫夫曼树
let node1 = new TreeNode('A', 17, null, null, null);
let node2 = new TreeNode('B', 2, null, null, null);
let node3 = new TreeNode('C', 49, null, null, null);
let node4 = new TreeNode('D', 11, null, null, null);
let node5 = new TreeNode('E', 5, null, null, null);
let node6 = new TreeNode('F', 16, null, null, null);
let nodes = new Array(node1, node2, node3, node4, node5, node6);
let treeCode = new HuffmanCode(nodes);
// 得到编码
let codes = treeCode.getAllCharCode();
for (let key of codes.keys()) {
	console.log('字符：' + key + ' 编码：' + codes.get(key));
}